//
//  Problem343.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/7.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*

 343. 整数拆分 【动态规划】【数学】【拆分整数】
 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

 示例 1:
     输入: 2
     输出: 1
     解释: 2 = 1 + 1, 1 × 1 = 1。
 示例 2:
     输入: 10
     输出: 36
     解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 说明: 你可以假设 n 不小于 2 且不大于 58。
 */
@objcMembers class Problem343: NSObject {
    func solution() {
        print(integerBreak(10))
    }
    
    /*
     动态规划
     1: 创建一个数组dp[n]
     2: dp[i]: i的最大乘积
     3: dp[i] = max(dp[i-1] * 1, i-1 * 1, dp[i-2]*2, i-2 * 2 ...)
     */
    func integerBreak(_ n: Int) -> Int {
        if n == 2 {
            return 1
        }
//        else if n == 10 {
//            return 36
//        }
        var dp = Array(repeating: 0, count: n+1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1
        let value = integerBreakDP(n, &dp)
        print(dp)
        return value
    }
    
    func integerBreakDP(_ n: Int, _ dp: inout [Int]) -> Int {
        if dp[n] != 0 {
            return dp[n]
        }
        for i in 1..<n {

            if i > (n - i) {
                break
            }
            dp[n] = max(dp[n], i * (n - i))
            dp[n] = max(dp[n], i * integerBreakDP(n - i, &dp))
        }
        
        return dp[n]
    }
}
